package h0806;

import java.util.*;

/**
  * @description 猜密码
  * @author 不知名帅哥
  * @date 2024/8/6 9:11
  * @version 1.0
*/
public class GuessPassword {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int[] nums = Arrays.stream(sc.nextLine().split(",")).mapToInt(Integer::parseInt).toArray();
        //密码最小数字数量
        int minLen=sc.nextInt();
        List<LinkedList<Integer>> res = getRes(nums, minLen);
        for (LinkedList<Integer> list : res) {
            StringJoiner joiner=new StringJoiner(",");
            for (Integer i : list) {
                joiner.add(i+"");
            }
            System.out.println(joiner);
        }
    }

    private static List<LinkedList<Integer>> getRes(int[] nums, int minLen) {
        List<LinkedList<Integer>> res=new ArrayList<>();
        Arrays.sort(nums);
        backtrack(nums,0,minLen,res,new LinkedList<>());
        return res;
    }

    private static void backtrack(int[] nums, int i, int minLen, List<LinkedList<Integer>> res,LinkedList<Integer> currentCombinations) {
        if (currentCombinations.size()>=minLen){
            res.add(new LinkedList<>(currentCombinations));
        }
        //提前剪枝，如果当前组合长度加上剩余可选数字的长度小于最小长度，则返回。
        if (currentCombinations.size()+(nums.length-i)<minLen) return;
        //横向的for循环
        //递归，纵向遍历
        for (int j = i; j < nums.length; j++) {
            //TODO 树层去重，去掉重复的组合
            if (j>0&&nums[j]==nums[j-1]){
                continue;
            }
            currentCombinations.add(nums[j]);
            backtrack(nums,j+1,minLen,res,currentCombinations);
            //这里进行回溯
            currentCombinations.removeLast();
        }
    }
}
